Time Complexity Analysis

We analyze the algorithm’s efficiency by determining the number of times some basic operation is done as a function of the size of the input. In general, a time complexity analysis of an algorithm is the determination of how many times the basic operation is done for each value of the input size.

알고리즘의 복잡도 분석은 각 입력크기 대해 기본연산이 수행된 횟수를 결정하는 것이다. 이를 결정함으로써 알고리즘의 효율성 분석이 가능하다.

T(n): Every-Case Time Complexity (모든 경우를 분석)

• T(n) is defined as the number of times the algorithm does the basic operation for an instance of size n.
• T(n) is called the every-case time complexity of the algorithm, and the determination of T(n) is called an every-case time complexity analysis.

모든 경우 분석. 입력크기에 종속되지만 입력값과는 무관하게 결과값은 항상 일정하다.
e.g. Add array members $\rightarrow$ T(n) = n
e.g. Matrix multiplication $\rightarrow$ T(n) = n^3

W(n): Worst-Case Time Complexity (최악의 경우를 분석)

• W(n) is defined as the maximum number of times the algorithm will ever do its basic operation for an input size of n.
• So W(n) is called the worst-case time complexity of the algorithm, and the determination of W(n) is called a worst-case time complexity analysis.

입력크기와 입력값 모두에 종속되며 단위연산 수행횟수가 최대인 경우 선택한다.
e.g. Sequential Search $\rightarrow$ W(n) = n

A(n): Average-Case Time Complexity (평균의 경우를 분석)

• A(n) is defined as the average (expected value) of the number of times the algorithm does the basic operation for an input size of n.
• A(n) is called the average-case time complexity of the algorithm, and the determination of A(n) is called an average-case time complexity analysis.

입력크기와 입력값 모두에 종속되며 모든 입력에 대해서 단위연산이 수행되는 횟수가 평균이다. 일반적으로 worst-case보다 계산이 복잡하다.
e.g. Sequential Search $\rightarrow$ A(n) = (n + 1)/2

B(n): Best-Case Time Complexity (최선의 경우를 분석)

• B(n) is defined as the minimum number of times the algorithm will ever do its basic operation for an input size of n.
• So B(n) is called the best-case time complexity of the algorithm, and the determination of B(n) is called a best-case time complexity analysis.

입력크기와 입력값 모두에 종속되며 단위연산 수행횟수가 최소인 경우 선택한다.
e.g. Sequential Search $\rightarrow$ B(n) = 1